964C - Alternating Sum - CodeForces Solution

//jiudge: 26520: 1687343940
#include<iostream>
#include<string>
#include<cstring> 
using namespace std;
typedef long long ll;
const long long mod=1e9+9;
string s;
ll qpow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n>0)
    {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    ll n,a,b,k;
    cin>>n>>a>>b>>k;
    cin>>s;
    ll res=0;
    for(int i=0;i<s.size();++i)
    {
        int flag;
        s[i]=='+'?flag=1:flag=-1;
     res=  ((res+flag*qpow(a, n-i, mod) * qpow(b, i, mod) )% mod  + mod) % mod;
    }

ll t = qpow(b, k, mod) * qpow(a, k * (mod - 2), mod) % mod;
    if (t == 1)
    {
        res = res * ((n + 1) / k) % mod;
    }
    else
    {
        res = res * (qpow(t, (n+1)/k, mod) - 1) % mod * qpow(t-1, mod - 2, mod) % mod;
    }
    cout<<res;
    return 0;
 }